package partition

import "container/list"

func move(src, tar *list.List) {
	e := src.Back()
	tar.PushBack(e.Value)
	src.Remove(e)
}

// 求解汉诺塔问题 f(i)
func dfsHanota(i int, src, buf, tar *list.List) {
	if i == 1 {
		move(src, tar)
		return
	}

	// 拆分为f(i - 1)和f(1)的问题

	//将i-1看做一个整体，先将i-1放到buf上
	dfsHanota(i-1, src, tar, buf)
	// 将最后一个放到tar上
	move(src, tar)
	//将 i-1的整体从buf放到tar上
	dfsHanota(i-1, buf, src, tar)
}

func SolveHanota(a, b, c *list.List) {
	dfsHanota(a.Len(), a, b, c)
}
